package nowCoder;
//package nowcoder;
//
//import java.util.ArrayList;
//import java.util.LinkedList;
//import java.util.Queue;
//
///**
//* Created by Ghost on 2015/4/8.
//*/
//
//public class ReConstructBinaryTree {
//    class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode(int x) { val = x; }
//    }
//    public TreeNode reConstructBinaryTree(ArrayList<Integer> pre,ArrayList<Integer> in) {
//        Integer[] preArr = new Integer[pre.size()];
//        preArr = pre.toArray(preArr);
//        Integer[] inArr = new Integer[in.size()];
//        inArr = in.toArray(inArr);
//        TreeNode root = new TreeNode(preArr[0]);
//        int fatherIdxIn = findIdx(inArr, root.val);
//        inArr[findIdx(inArr,root.val)] = -1;
//        construct(root, root, preArr, inArr, 1, fatherIdxIn);
//        return root;
//    }
//
//    private void construct(TreeNode rstRoot,TreeNode root, Integer[] pre, Integer[] in, int currentPreIdx, int fatherIdxIn){
//        if(currentPreIdx==pre.length)
//            return ;
//        TreeNode current = new TreeNode(pre[currentPreIdx]);
//        int currentIdxIn = findIdx(in, pre[currentPreIdx]);
//        if(currentIdxIn<fatherIdxIn){
//            int min = in.length;
//            for(int i=fatherIdxIn;i>=0 && i>currentIdxIn;i--){
//                if(in[i]==-1){
//                    if(min>i)
//                        min=i;
//                }
//            }
//            TreeNode node = findNode(rstRoot, in[min]);
//            node.left = current;
//            in[min]=-1;
//        } else{
//
//            int max = 0;
//            for(int i=fatherIdxIn;i<in.length && i<currentIdxIn;i++){
//                if(in[i]==-1){
//                    if(max<i)
//                        max=i;
//                }
//            }
//            TreeNode node = findNode(rstRoot, in[max]);
//            node.right = current;
//            in[max] = -1;
//        }
//
//        construct(rstRoot,current, pre, in, currentPreIdx+1, currentIdxIn);
//    }
//    private TreeNode findNode(TreeNode rstRoot, int target){
//        Queue<TreeNode> queue = new LinkedList<TreeNode>();
//        TreeNode node = rstRoot;
//        while(node.val!=target){
//            if(node.left!=null)
//                queue.add(node.left);
//            if(node.right!=null)
//                queue.add(node.right);
//            node = queue.poll();
//        }
//        return node;
//    }
//    private int findIdx(Integer[] in, int val){
//        for(int i=0;i<in.length;i++)
//            if(in[i]==val)
//                return i;
//        return -1;
//    }
//    public static void main(String[] args){
//        ReConstructBinaryTree reConstructBinaryTree = new ReConstructBinaryTree();
//        ArrayList<Integer> pre = new ArrayList<Integer>();
//        pre.add(1);
//        pre.add(2);
//        pre.add(4);
//        pre.add(7);
//        pre.add(3);
//        pre.add(5);
//        pre.add(6);
//        pre.add(8);
//        ArrayList<Integer> in = new ArrayList<Integer>();
//        in.add(4);
//        in.add(7);
//        in.add(2);
//        in.add(1);
//        in.add(5);
//        in.add(3);
//        in.add(8);
//        in.add(6);
//
//        TreeNode root = reConstructBinaryTree.reConstructBinaryTree(pre, in);
//        System.out.println(root);
//    }
//}
